﻿
namespace Leetcode.N0675;

public class Solution
{
    public int CutOffTree(IList<IList<int>> forest)
    {
        var trees = this.GetTrees(forest);
        int steps = 0;
        var from = (0, 0);

        for (int i = 0; i < trees.Length; i++)
        {
            if (!this.TryCut(forest, from, trees[i], ref steps))
            {
                return -1;
            }
            from = trees[i];
        }

        return steps;
    }

    private (int row, int col)[] GetTrees(IList<IList<int>> forest)
    {
        var trees = new List<(int row, int col)>();
        for (int row = 0; row < forest.Count; row++)
        {
            for (int col = 0; col < forest[row].Count; col++)
            {
                if (forest[row][col] <= 1)
                {
                    continue;
                }
                trees.Add((row, col));
            }
        }
        return trees.OrderBy(_ => forest[_.row][_.col]).ToArray();
    }

    private bool TryCut(IList<IList<int>> forest, (int row, int col) from, (int row, int col) to, ref int steps)
    {
        var (n, m) = (forest.Count, forest[0].Count);
        var visited = new bool[n, m];
        var queue = new Queue<(int row, int col)>();
        queue.Enqueue(from);
        visited[from.row, from.col] = true;

        void Enqueue(int row, int col)
        {
            if (row < 0 || row >= n || col < 0 || col >= m || forest[row][col] == 0
              || visited[row, col])
            {
                return;
            }

            visited[row, col] = true;
            queue.Enqueue((row, col));
        }

        while (queue.Count > 0)
        {
            var items = new List<(int row, int col)>();
            while (queue.Count > 0)
            {
                var item = queue.Dequeue();
                if (item.row == to.row && item.col == to.col)
                {
                    return true;
                }
                items.Add(item);
            }

            foreach (var item in items)
            {
                Enqueue(item.row - 1, item.col);
                Enqueue(item.row + 1, item.col);
                Enqueue(item.row, item.col - 1);
                Enqueue(item.row, item.col + 1);
            }
            steps++;
        }

        return false;
    }
}
